#include<iostream>
#include<vector>
#include<deque>
#include<unordered_map>
using namespace std;

class Node {
public:
	int val;
	vector<Node*> neighbors;
	Node() {
		val = 0;
		neighbors = vector<Node*>();
	}
	Node(int _val) {
		val = _val;
		neighbors = vector<Node*>();
	}
	Node(int _val, vector<Node*> _neighbors) {
		val = _val;
		neighbors = _neighbors;
	}
};

class Solution {
public:
	unordered_map<Node *, Node *> reflct;
	Node* cloneGraph(Node* node) {
		if (node == NULL) {
			return NULL;
		}
		if (reflct.find(node) != reflct.end()) {
			return reflct[node];
		}
		Node *newnode = new Node(node->val);
		reflct[node] = newnode;
		for (Node * child : node->neighbors) {
			newnode->neighbors.push_back(cloneGraph(child));
		}
		return newnode;
	}
};

void main() {
	Node n1(1), n2(2), n3(3), n4(4);
	n1.neighbors.push_back(&n2);
	n1.neighbors.push_back(&n4);
	n2.neighbors.push_back(&n1);
	n2.neighbors.push_back(&n3);
	n3.neighbors.push_back(&n2);
	n3.neighbors.push_back(&n4);
	n4.neighbors.push_back(&n1);
	n4.neighbors.push_back(&n3);
	Solution s;
	Node *newgraph=s.cloneGraph(&n1);
	cout << "Done" << endl;
}